#include <stdio.h>
#include <stdlib.h>

/**
 * 树是基本的数据结构，在数据存储，构建索引等方面有着很大的用处
 * 树一般指二叉树，我们只实现最简单的树操作
 *
 * 分析树的一个节点，包括父节点，左子节点，右子节点
 * 设置父节点为 1，左子节点为2，右子节点为3，则左子节点可表示为2*n，右子节点可表示为2*n+1
 *
 * 我们实现的主要功能如下：
 * 1.创建树
 * 2.递归实现先序打印树
 * 3.递归实现中序打印树
 * 4.递归实现后序打印树
 * 5.栈实现先序打印树
 * 6.栈实现中序打印树
 * 7.栈实现后序打印树
 * 8.层次打印树
 *
 *
 */
typedef int data_t;
typedef struct Tree {
    data_t data;
    struct Tree *lchild;
    struct Tree *rchild;
} tree_t;

tree_t *create_tree(int nodeid, int nodetotal)
{
    tree_t *root;
    if(nodeid > nodetotal) return NULL;

    root = malloc(sizeof(tree_t));
    root->data = nodeid;

    root->lchild = create_tree(2 * nodeid, nodetotal);
    root->rchild = create_tree(2 * nodeid + 1, nodetotal);
    return root;
}

void print_pre(tree_t *root)
{
    printf("%d ", root->data);
    if(NULL != root->lchild) print_pre(root->lchild);
    if(NULL != root->rchild) print_pre(root->rchild);
}

void print_mid(tree_t *root)
{
    if(NULL != root->lchild) print_mid(root->lchild);
    printf("%d ", root->data);
    if(NULL != root->rchild) print_mid(root->rchild);
}

void print_post(tree_t *root)
{
    if(NULL != root->lchild) print_post(root->lchild);
    if(NULL != root->rchild) print_post(root->rchild);
    printf("%d ", root->data);
}

//栈排序
void print_pre_stack(tree_t *root) 
{
    int top = -1;
    tree_t *stack[1000];

    while(NULL != root || top != -1) { 
        while(NULL != root) {
            printf("%d ", root->data);
            stack[++top] = root;
            root = root->lchild;
        }
        root = stack[top--];
        root = root->rchild;
    }
}

void print_mid_stack(tree_t *root)
{
    int top = -1;
    tree_t *stack[1000];
    while(NULL != root || top != -1) {
        while(NULL != root) {
            stack[++top] = root;
            root = root->lchild;
        }
        root = stack[top--];
        printf("%d ", root->data);
        root = root->rchild;
    }
}

void print_post_stack(tree_t *root) 
{
    struct {
        tree_t *root;
        int flag;
    } stack[1000], buf;
    int top = -1;
    while(NULL != root || top != -1) {
        while(NULL != root) {
            buf.root = root;
            buf.flag = 1;
            stack[++top] = buf;
            root = root->lchild;
        }
        buf = stack[top--];
        if(1 == buf.flag) {
            root = buf.root->rchild;
            buf.flag = 2;
            stack[++top] = buf;
        } else if(2 == buf.flag) {
            printf("%d ", buf.root->data);
        }
    }
}

void print_level(tree_t *root) 
{
    tree_t * * queue;
    int head = 0;
    int tail = 0;

    queue = malloc(sizeof(tree_t *) * 1000);

    queue[tail ++] = root;

    while(tail != head) {
        root = queue[head++];
        if(NULL != root->lchild) queue[tail++] = root->lchild;
        if(NULL != root->rchild) queue[tail++] = root->rchild;
        printf("%d ", root->data);
    }
}

int main(int args, const char *argv[])
{
    tree_t *root;
    root = create_tree(1, 6);

    printf("\n先序遍历：");
    print_pre(root);
    printf("\n中序遍历：");
    print_mid(root);
    printf("\n后序遍历：");
    print_post(root);

    printf("\n栈先序遍历：");
    print_pre_stack(root);
    printf("\n栈中序遍历：");
    print_mid_stack(root);
    printf("\n栈后序遍历：");
    print_post_stack(root);

    printf("\n层次遍历：");
    print_level(root);

    return 0;
}


